#define DEBUG
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long ll;
const int maxk=7, maxn=200;
int tab[maxk+1][20], tabs[maxk+1][1000][2];

bool check(int o, int n, int k) {
  if (!o && !k) return true;
  else if (!o^!k) return false;
  else {
    for (int i=1; i<=sqrt(n); i++) {
      if (n%i==0 && ((o>=n/i && check(o-n/i, n, k-1)) || (o>=i && check(o-i, n, k-1)))) return true;
    }
    return false;
  }
}

int gcd(int a, int b) {
  for (int r=a%b; r; a=b, b=r, r=a%b);
  return b;
}

int lcm(int a, int b) {
  return a/gcd(a, b)*b;
}

void makeTab(int n, int k, int tab[]) {
  static bool book[maxn+1];
  memset(book, 0, sizeof book);
  for (int i=1; i<=n; i++) {
    if (!book[i]) {
      if (check(i, i, k)) {
        tab[++tab[0]] = i;
        for (int j=1; i*j<=n; j++) {
          book[i*j] = true;
        }
      }
    }
  }
}

void makeTabs(int o, int x, int now, int tab[], int tabs[][2]) {
  if (o<=tab[0]) {
    makeTabs(o+1, x, now, tab, tabs);
    makeTabs(o+1, -x, lcm(now, tab[o]), tab, tabs);
  } else if (now>1) {
    for (int i=1; i<=tabs[0][0]; i++) {
      if (tabs[i][0]==now) {
        tabs[i][1]+=x;
        return;
      }
    }
    tabs[++tabs[0][0]][0] = now;
    tabs[tabs[0][0]][1] = x;
  }
}

ll f(ll n, int tabs[][2]) {
  ll ret=0;
  for (int i=1; i<=tabs[0][0]; i++) {
    ret += n/tabs[i][0]*tabs[i][1];
  }
  return ret;
}

int main() {
#ifdef DEBUG
  freopen("src.in", "r", stdin);
  freopen("src.out", "w", stdout);
#endif

  for (int i=2; i<=maxk; i++) {
    makeTab(maxn, i, tab[i]);
    makeTabs(1, -1, 1, tab[i], tabs[i]);
  }

  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    ll a, b;
    int k;
    scanf("%lld %lld %d", &a, &b, &k);
    printf("%lld\n", f(b, tabs[k])-f(a-1, tabs[k]));
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
